N-ary trees quickly become very wide structures that are difficult to display on computer terminals. When fully populated, the number of nodes at the lowest level in the tree equals n.sup.h where n is the number of children in each node and h is the height of the tree. If n=8 and h=3 this will, for example, result in 512 nodes which is very difficult to visualise and clearly impossible to display on a conventional display screen.
In the prior art, zooming and/or scrolling techniques have been used to enable the user to view the tree at a reduced scale or in a fragmentary way. These can be illustrated by taking a more simple example than that given above in which each node has four children and the tree has a height of 3. Such a structure is very regular, which is not typical of tree data structures but it is used to depict the worst case width of such a tree. FIG. 1 shows how such a tree would be shown on a display screen.
In this depicted example, it would be impossible for the observer of the tree to read any captions or information associated with each node of the tree. FIG. 2 shows an example when zooming techniques are used to view a part of the tree structure of FIG. 1. Clearly one has gained on detail, however it is difficult to recognize what area of the tree is presented.
Sometimes the view of FIG. 2 is combined on the display screen with a small scale picture of the complete tree structure as is shown in FIG. 3. A rectangle is superimposed on the small scale picture of the complete tree structure to indicate the portion of the tree structure that is currently shown in the main part of the display screen.
The disadvantage of using scrolling and zooming techniques is that it is extremely difficult to navigate through the tree structure. Taking the display of FIG. 3 as an example and supposing that the portion of the tree structure which the observer wishes to view is not the portion that is displayed in the main part of the display screen, then it can take up to five attempts to display the desired portion of the tree structure if one starts at the left hand side of the bottom row of the tree structure and the desired portion is on the right hand side of the tree structure. This form of display and navigation clearly does not lend itself to a systematic approach of finding ones way in a hierarchical structure.
Known from the published prior art are various means of depicting tree structures. For example U.S. Pat. No. 4,710,763 (Franke et al) discloses a method for constructing and displaying tree structures with automated data processing equipment. The method taught in this patent is to provide a focused view of a portion of the tree to enable an observer to perform editing and evaluating functions on the displayed tree structure. The focused view present a view of a portion of the tree structure with a geometry different that that which would be used if the entire tree structure were displayed. This provides a view of a portion of the tree which is highly readable but does not allow the observer to perceive the position of the portion of the tree within the entire tree structure.
In the IBM Technical Disclosure Bulletin, vol 34, no 8, January 1992, pp 432-433, an article entitled "Hierarchical Menu Display Structure" teaches the display of a menu system in tree form and a method for controlling the menu system. The article does not, however, teach how the display of the menu system in tree form is optimised on the display screen.
An article in the IBM Technical Disclosure Bulletin, vol 34, no 4A, September 1991, pp 402-404, entitled "Efficient Display of Tree-form Data on VDU or Printer" teaches a method of producing tree-form diagrams which can be used both with fixed and proportionally spaced character fonts. In this article, a method for displaying trees whose nodes consist of alphanumeric characters is described. The teachings are, however, not applicable to tree structures in which the nodes may also be presented in the form of bitmaps or icons.